//链表判环

//方法一：哈希表
//遍历所有节点，每次遍历到一个节点时，判断该节点此前是否被访问过。使用哈希表来存储所有已经访问过的节点。
//每次我们到达一个节点，如果该节点已经存在于哈希表中，则说明该链表是环形链表，否则就将该节点加入哈希表中。
//重复这一过程，直到我们遍历完整个链表即可。
//时间复杂度O(n)，空间复杂度O(1)  
/**
 *  Definition for singly-linked list.
 *  struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 *  };
 *  */
class Solution {
    public:
        bool hasCycle(ListNode *head)
        {
            unordered_set<ListNode*> uset;
            while(head!=nullptr)
            {
                //unordered_set 不允许元素重复
                //unordered_set.count(key)：检查容器中是否存在key
                if(uset.count(head))
                    return true;
                uset.insert(head);
                head=head->next;
            }
            return false;
        }


//方法二：快慢指针
//准备两个指针：一个快指针，一个慢指针。
//两个指针初始都指向head，开始遍历链表，快指针每次走两步，慢指针每次走一步，
//如果快指针先抵达终点成为NULL，则说明没有环；如果快指针会和慢指针相遇，则说明有环。
//时间复杂度O(n)，空间复杂度O(1)
class Solution {
    public:
        bool hasCycle(ListNode *head)
        {
            //使用快慢指针法
            //若头节点为null，直接返回false
            if (head == nullptr)
                return false;
            //1.声明两个步子不同的快慢指针
            ListNode* fast = head;
            ListNode* slow = head;
            //2.循环进行判断   fast和fast->next需要不为空，否则会发生非法内存访问
            while(fast!=nullptr&&fast->next!=nullptr){
                //快指针一步两个节点，慢指针一个
                fast = fast->next->next;
                slow = slow->next;
                //当快慢指针相等时，链表中有环
                if(fast == slow)
                    return true;
            }
            //当fast/fast->next为null时，链表中没有环，操作结束
            return false;
        }
};

};
